from __future__ import print_function
from .compat import *
import os, string

class Symbol :
    _age = {}
    _next = 0
    _new = {}
    def __init__ (self, name, final=True, value=None, children=None) :
        if name not in Symbol._age :
            Symbol._age[name] = Symbol._next
            Symbol._next += 1
        self.__dict__["name"] = name
        self.__dict__["final"] = final
        self.value = value
        self.children = children
    def __setattr__ (self, name, value) :
        if name in ["name", "final"] :
            raise ValueError("non mutable attribute")
        else :
            self.__dict__[name] = value
    def __hash__ (self) :
        return hash((self.name, self.final))
    def __equal__ (self, other) :
        return (self.name, self.final) == (other.name, other.final)
    def __str__ (self) :
        if self.value is None :
            return self.name
        else :
            return "%s:%s" % (self.name, str(self.value))
    def __len__ (self) :
        if self.children is None :
            return 0
        else :
            return len(self.children)
    def _repr (self) :
        if self.children is None :
            return [self.__str__()]
        else :
            lines = []
            count = 0
            for child in self.children :
                for line in child._repr() :
                    if line[0] not in "| " :
                        lines.append("|-> " + line)
                        count += 1
                    elif count >= len(self.children) :
                        lines.append("    " + line)
                    else :
                        lines.append("|   " + line)
            return [self.__str__()] + lines
    def __repr__ (self) :
        return "\n".join(self._repr())
    def _draw (self, out) :
        print('"n%s" [' % id(self), file=out)
        print('  label = "%s"' % str(self), file=out)
        if self.final :
            print('  shape = "rect"', file=out)
        else :
            print('  shape = "ellipse"', file=out)
        print(']', file=out)
        if self.children is not None :
            for child in self.children :
                child._draw(out)
                print('"n%s" -> "n%s" []' % (id(self), id(child)), file=out)
    def draw (self, name, format="png") :
        if format == "eps" :
            format = "ps"
        if format == "ps" :
            outfile = "%s.eps" % name
        else :
            outfile = "%s.%s" % (name, format)
        if format == "dot" :
            out = open(outfile, "w")
        else :
            out = open(outfile + ".dot", "w")
        print('digraph "(%s)" {' % str(self), file=out)
        self._draw(out)
        print("}", file=out)
        out.close()
        if format != "dot" :
            os.system("dot -T%s -o %s %s" % (format, outfile, out.name))
            os.system("rm -f %s.dot" % outfile)
    def parent (self, children) :
        if children is not None :
            children = list(children)
            if len(children) == 0 :
                children = None
        return Symbol(self.name, self.final, self.value, children)
    def copy (self) :
        result = self.parent(self.children)
        for attr in dir(self) :
            if not hasattr(result, attr) :
                setattr(result, attr, getattr(self, attr))
        return result
    def new (cls, base) :
        basename = base.name.rstrip("0123456789")
        i = cls._new.get(basename, 0)
        while True :
            name = basename + str(i)
            if name not in cls._age :
                break
            i += 1
        cls._new[basename] = i
        return Symbol(name, final=base.final)
    new = classmethod(new)
    def __cmp__ (self, other) :
        return int.__cmp__(Symbol._age[self.name], Symbol._age[other.name])
    def __eq__ (self, other) :
        return self.name == other.name

epsilon = Symbol("~")
EOF = Symbol("$")

def _symbols (symbols) :
    if len(symbols) == 0 :
        return str(epsilon)
    else :
        return " ".join([str(s) for s in symbols])

def _rule (left, right) :
    return "%s -> %s" % (str(left), _symbols(right))

def _item (item) :
    left, head, tail = item
    return "%s -> %s @ %s" % (left, _symbols(head), _symbols(tail))

def _action (action, args) :
    if action in ["goto", "shift"] :
        return "%s(%s)" % (action, args)
    elif action == "reduce" :
        return "reduce(%s)" % _rule(*args)
    elif action == "accept" :
        return action
    else :
        return str(action, args)

class Table :
    def __init__ (self, gram) :
        self._t = {}
        self._g = gram
    def __setitem__ (self, key, value) :
        if key in self._t :
            raise KeyError("exists")
        self._t[key] = value
    def __getitem__ (self, key) :
        return self._t.get(key, None)
    def __iter__ (self) :
        return iter(self._t)
    def __len__ (self) :
        return len(self._t)
    def __str__ (self) :
        lin = set()
        col = set([EOF])
        for l, c in self._t :
            lin.add(l)
            col.add(c)
        lin = list(sorted(lin))
        col = list(sorted(col))
        width = {}
        for c in col :
            w = len(str(c))
            for l in lin :
                if (l, c) in self._t :
                    w = max(w, len(self._str(self[(l, c)])))
            width[c] = w
        w = 0
        for l in lin :
            w = max(w, len(str(l)))
        width[0] = w
        lines = []
        parts = [" " * width[0]]
        for c in col :
            parts.append(str(c).ljust(width[c]))
        lines.append(" | ".join(parts))
        parts = ["-" * width[0]]
        for c in col :
            parts.append("-" * width[c])
        lines.append("---".join(parts))
        for l in lin :
            parts = [str(l).ljust(width[0])]
            for c in col :
                if (l, c) in self._t :
                    parts.append(self._str(self[(l, c)]).ljust(width[c]))
                else :
                    parts.append(" " * width[c])
            lines.append(" | ".join(parts))
        return "\n".join(lines)
    def __repr__ (self) :
        lines = [str(self._g), ""]
        for s in self._g._rules :
            lines.append("First(%s) = %s" % (str(s), " ".join([str(x) for x in self._g.first(s)])))
            lines.append("Next(%s) = %s" % (str(s),  " ".join([str(x) for x in self._g.next(s)])))
        lines.extend(["", str(self)])
        return "\n".join(lines)

class LL1 (Table) :
    def __setitem__ (self, key, value) :
        try :
            Table.__setitem__(self, key, value)
        except KeyError :
            raise ValueError("not LL(1)")
    def _str (self, cell) :
        return _symbols(cell)
    def match (self, tokens, verbose=False) :
        tokens = list(tokens) + [EOF]
        root = self._g.start.copy()
        stack = [EOF, root]
        while True :
            if verbose :
                print("stack:", _symbols(stack))
                print("input:", _symbols(tokens))
            X = stack[-1]
            a = tokens[0]
            if X.final :
                if X == EOF :
                    if a == EOF :
                        if verbose :
                            print("EOF => accept")
                        return root
                    else :
                        if verbose :
                            print("EOF expected => reject")
                        return None
                else :
                    if X == a :
                        if verbose :
                            print("match:", a)
                        stack.pop(-1).value = tokens.pop(0).value
                    else :
                        if verbose :
                            print(X, "expected => reject")
                        return None
            else :
                right = self[(X, a)]
                if right is None :
                    if verbose :
                        print("no matching rule => reject")
                    return None
                else :
                    if verbose :
                        print("apply:", _rule(X, right))
                    top = stack.pop(-1)
                    top.children = [s.copy() for s in right]
                    stack.extend(reversed(top.children))
                    if len(top.children) == 0 :
                        top.children.append(epsilon.copy())
            if verbose :
                print()

def action2str (action, left, right) :
    d = {"L" : str(left)}
    for i, r in enumerate(right) :
        d["R%s" % i] = str(r)
    try :
        return string.Template(action.__doc__).substitute(d)
    except :
        return "%s(%s, %s)" % (action.__name__, str(left),
                               ", ".join([str(r) for r in right]))

class SLR (Table) :
    def __setitem__ (self, key, value) :
        try :
            Table.__setitem__(self, key, value)
        except KeyError :
            raise ValueError("LR conflict: %s / %s" % (_action(*self[key]),
                                                        _action(*value)))
    def __getitem__ (self, key) :
        return self._t.get(key, (None, None))
    def _str (self, cell) :
        action, args = cell
        if action == "accept" :
            return "accept"
        elif action in ["shift", "goto"] :
            return " ".join([action, str(args)])
        elif action == "reduce" :
            return "reduce " + _rule(*args)
    def match (self, tokens, verbose=False) :
        tokens = list(tokens) + [EOF]
        stack = [EOF, 0]
        while True :
            if verbose :
                print("stack:", _symbols(stack))
                print("input:", _symbols(tokens))
            X = stack[-1]
            a = tokens[0]
            if type(X) is int :
                action, args = self[(X, a)]
                if action == "accept" :
                    if verbose :
                        print("apply: accept")
                    return stack[-2]
                elif action == "shift" :
                    if verbose :
                        print("apply: shift", a, args)
                    stack.append(a)
                    stack.append(args)
                    tokens.pop(0)
                elif action == "reduce" :
                    if verbose :
                        print("apply: reduce", _rule(*args))
                    stack.pop(-1)
                    left, right = args
                    children = []
                    for symbol in reversed(right) :
                        if type(stack[-1]) is int :
                            stack.pop(-1)
                        if stack[-1] != symbol :
                            if verbose :
                                "=> reject"
                            return None
                        children.append(stack.pop(-1).copy())
                    new = left.parent(reversed([c.copy() for c in children]))
                    if len(children) == 0 :
                        new.children.append(epsilon.copy())
                    stack.append(new)
                    action = self._g.action[args]
                    if action is not None :
                        _args = tuple(reversed(children))
                        if verbose :
                            print("action:", action2str(action, new, _args))
                        action(new, _args)
                else :
                    if verbose :
                        print("=> reject")
                    return None
            else :
                for obj in reversed(stack) :
                    if type(obj) is int :
                        state = obj
                        break
                action, args = self[(state, X)]
                if action == "goto" :
                    if verbose :
                        print("apply: goto", args)
                    stack.append(args)
                else :
                    if verbose :
                        print("=> reject")
                    return None
            if verbose :
                print()
    def __repr__ (self) :
        lines = [str(self._g), ""]
        for s in self._g._rules :
            lines.append("Next(%s) = %s" % (str(s),  " ".join([str(x) for x in self._g.next(s)])))
        lines.extend(["", str(self)])
        return "\n".join(lines)

def _best_prefix (productions) :
    prods = set(productions)
    pref = {}
    while len(prods) > 0 :
        p = prods.pop()
        if len(p) == 0 :
            continue
        elif p[0] in pref :
            pref[p[0]].add(p)
        else :
            pref[p[0]] = set([p])
    best = tuple()
    for symbol, prods in list(pref.items()) :
        if len(prods) > 1 :
            suite = _best_prefix([p[1:] for p in prods])
            if len(suite)+1 > len(best) :
                best = (symbol,) + suite
    return best

class Grammar :
    def __init__ (self) :
        self._rules = {}
        self.start = None
        self._first = {tuple() : set([epsilon]), epsilon : set([epsilon])}
        self._next = {}
        self.action = {}
    def symbols (self, final=False) :
        result = set()
        for left, right in self :
            result.add(left)
            if final :
                for symb in right :
                    result.add(symb)
        return list(result)
    def add (self, left, right, action=None) :
        if right == [left] :
            raise ValueError("infinite recursion")
        self._first = {tuple() : set([epsilon]), epsilon : set([epsilon])}
        self._next = {}
        if left not in self._rules :
            self._rules[left] = set()
        self._rules[left].add(tuple(right))
        if self.start is None :
            self.start = left
        self.action[(left, tuple(right))] = action
    def remove (self, left, right) :
        self._rules[left].remove(tuple(right))
        if len(self._rules[left]) == 0 :
            del self._rules[left]
        self._first = {tuple() : set([epsilon]), epsilon : set([epsilon])}
        self._next = {}
        del self.action[(left, tuple(right))]
    def __iter__ (self) :
        result = []
        for left, prods in list(self._rules.items()) :
            for right in prods :
                result.append((left, right))
        return iter(result)
    def copy (self) :
        result = Grammar()
        result.start = self.start
        for left, right in self :
            result.add(left, right)
        result._first = self._first.copy()
        result._next = self._next.copy()
        result.action = self.action.copy()
        return result
    def __str__ (self) :
        lines = ["start = %s" % self.start]
        for left in self._rules :
            first = True
            for right in self._rules[left] :
                if first :
                    line = "%s ::= " % left
                    first = False
                else :
                    line = "|  ".rjust(len(left.name) + 5)
                lines.append(line + _symbols(right))
        return "\n".join(lines)
    def __getitem__ (self, left) :
        return self._rules[left]
    def _recursive (self, symbol) :
        queue = [symbol]
        visited = set()
        while len(queue) > 0 :
            current = queue.pop()
            visited.add(current)
            for prod in self._rules[current] :
                if len(prod) == 0 :
                    continue
                elif prod[0].final :
                    continue
                elif prod[0] == symbol :
                    return True
                elif prod[0] not in visited :
                    queue.append(prod[0])
        return False
    def recursive (self) :
        for symbol in list(self._rules.keys()) :
            if self._recursive(symbol) :
                return True
        return False
    def _derecursify (self, symbol, result, verbose) :
        recursive = set()
        alternate = set()
        for prod in result._rules[symbol] :
            if len(prod) == 0 :
                alternate.add(prod)
            elif prod[0] == symbol :
                recursive.add(prod)
            else :
                alternate.add(prod)
        if len(recursive) == 0 :
            return
        new = Symbol.new(symbol)
        if verbose :
            print("replace:")
        for prod in alternate | recursive :
            if verbose :
                print("   ", _rule(symbol, prod))
            result.remove(symbol, prod)
        if verbose :
            print("with:")
        for rec in recursive :
            if verbose :
                print("   ", _rule(new, rec[1:] + (new,)))
            result.add(new, rec[1:] + (new,))
            for alt in alternate :
                if verbose :
                    print("   ", _rule(symbol, alt + (new,)))
                result.add(symbol, alt + (new,))
        if verbose :
            print("   ", _rule(new, []))
        result.add(new, [])
    def derecursify (self, symbols=None, verbose=False) :
        if verbose :
            print("*** removing left recursions")
        result = self.copy()
        if symbols is None :
            symbols = sorted(self._rules.keys())
        assert set(symbols) == set(self._rules.keys()), "invalid symbols"
        if verbose :
            print("order:", _symbols(symbols))
        for i, Ai in enumerate(symbols) :
            if verbose :
                print("current:", Ai)
            for Aj in symbols[:i] :
                if verbose :
                    print("try:", _rule(Ai, [Aj, "..."]))
                for prod in result._rules[Ai].copy() :
                    if (len(prod) == 0) or (prod[0] != Aj) :
                        result.add(Ai, prod)
                    else :
                        if verbose :
                            print("replace:", _rule(Ai, prod))
                        result.remove(Ai, prod)
                        for alt in result._rules[Aj].copy() :
                            if verbose :
                                print(" with:", _rule(Ai, alt + prod[1:]))
                            result.add(Ai, alt + prod[1:])
            self._derecursify(Ai, result, verbose)
        result.start = self.start
        return result
    def is_clean (self) :
        for left, right in self :
            if len(right) == 0 :
                return False
        return True
    def clean (self, verbose=False) :
        if verbose :
            print("*** cleaning")
        empty = set()
        update = {}
        for left, right in self :
            if len(right) == 0 :
                empty.add(left)
                update[left] = set()
                for l, r in self :
                    if left in r :
                        update[left].add((l, r))
        result = self.copy()
        for symbol in empty :
            if verbose :
                print("remove:", _rule(symbol, []))
            result.remove(symbol, [])
            queue = update[symbol]
            while len(queue) > 0 :
                left, right = queue.pop()
                right = list(right)
                i = -1
                while True :
                    try :
                        i = right[i+1:].index(symbol)+i+1
                    except ValueError :
                        break
                    new = right[:]
                    del new[i]
                    if symbol in new :
                        queue.add((symbol, tuple(new)))
                    if verbose :
                        print("create:", _rule(left, new))
                    result.add(left, new)
        return result
    def factorized (self) :
        first = {}
        for left, right in self :
            if len(right) == 0 :
                continue
            elif not right[0].final :
                continue
            elif left in first :
                if right[0] in first[left] :
                    return False
                first[left].add(right[0])
            else :
                first[left] = set([right[0]])
        return True
    def factorize (self, verbose=False) :
        if verbose :
            print("*** left factorizing")
        result = self.copy()
        queue = set(result._rules.keys())
        while len(queue) > 0  :
            left = queue.pop()
            while True :
                create, remove = set(), set()
                prefix = _best_prefix(result._rules[left])
                cut = len(prefix)
                if cut == 0 :
                    break
                new = Symbol.new(left)
                queue.add(new)
                if verbose :
                    print("found prefix", _rule(left, prefix))
                    print("  create:", _rule(left, prefix + (new,)))
                create.add((left, prefix + (new,)))
                for right in result._rules[left] :
                    if right[:cut] == prefix :
                        if verbose :
                            print("  replace:", _rule(left, right))
                            print("     with:", _rule(new, right[cut:]))
                        remove.add((left, right))
                        create.add((new, right[cut:]))
                for l, r in remove :
                    result.remove(l, r)
                for l, r in create :
                    result.add(l, r)
        return result
    def first (self, symbol, verbose=False) :
        if symbol in self._first :
            return self._first[symbol]
        elif isinstance(symbol, Symbol) :
            if symbol.final :
                if verbose :
                    print("first(%s) =" % symbol, symbol)
                self._first[symbol] = set([symbol])
                return self._first[symbol]
            result = set()
            for right in self._rules[symbol] :
                if verbose :
                    print(_rule(symbol, right), "=>", end=' ')
                if len(right) == 0 :
                    if verbose :
                        print("first(%s) +=" % symbol, epsilon)
                    result.add(epsilon)
                else :
                    if verbose :
                        print("first(%s) += first(%s)" % (symbol,
                                                          _symbols(right)))
                    result.update(self.first(right, verbose))
            self._first[symbol] = result
            return result
        else :
            result = set()
            next = False
            for s in symbol :
                if verbose :
                    print("first(%s) += first(%s)" % (_symbols(symbol), s))
                new = set(self.first(s, verbose))
                if epsilon in new :
                    next = True
                    new.remove(epsilon)
                result.update(new)
                if not next :
                    break
            if next :
                if verbose :
                    print("first(%s) +=" % symbol, epsilon)
                result.add(epsilon)
            self._first[symbol] = result
            return result
    def next (self, symbol, verbose=False) :
        if symbol in self._next :
            return self._next[symbol]
        for left in self._rules :
            self._next[left] = set()
        if verbose :
            print("\n*** computing next")
            print("next(%s) +=" % self.start, EOF)
        self._next[self.start].add(EOF)
        set_epsilon = set([epsilon])
        for left, right in self :
            for i in range(len(right)-1) :
                if not right[i].final :
                    if verbose :
                        print(("next(%s) += first(%s) - %s"
                               % (right[i],
                                  _symbols(right[i+1:]),
                                  epsilon)))
                    self._next[right[i]].update(self.first(right[i+1:], verbose)
                                                - set_epsilon)
        saturated = False
        while not saturated :
            saturated = True
            for left, right in self :
                if (len(right) > 0) and (not right[-1].final) :
                    last = right[-1]
                    if not (self._next[left] <= self._next[last]) :
                        saturated = False
                        if verbose :
                            print("next(%s) += next(%s)" % (last, left))
                        self._next[last].update(self._next[left])
                for i in range(len(right)-1) :
                    symb = right[i]
                    if symb.final :
                        continue
                    tail = right[i+1:]
                    if epsilon in self.first(tail, verbose) :
                        if not (self._next[left] <= self._next[symb]) :
                            saturated = False
                            if verbose :
                                print(("%s in first(%s) => next(%s) += next(%s)"
                                       % (epsilon, _symbols(tail), symb, left)))
                            self._next[symb].update(self._next[left])
        return self._next[symbol]
    def LL1 (self, verbose=False) :
        gram = self.copy()
        if verbose :
            display = not gram.is_clean()
        gram = gram.clean(verbose=verbose)
        if verbose :
            if display :
                print("\n*** result:")
                print(gram)
                print()
            display = gram.recursive()
        gram = gram.derecursify(verbose=verbose)
        if verbose :
            if display :
                print("\n*** result:")
                print(gram)
                print()
            display = not gram.factorized()
        gram = gram.factorize(verbose=verbose)
        if verbose :
            if display :
                print("\n*** result:")
                print(gram)
                print()
        gram.next(gram.start, verbose=verbose)
        if verbose :
            print("\n*** building LL(1) table")
        result = LL1(gram)
        for A, alpha in gram :
            if verbose :
                print("rule:", _rule(A, alpha))
            for a in gram.first(alpha, verbose) :
                if a != epsilon :
                    if verbose :
                        print(" => table[%s,%s] =" % (A, a), _rule(A, alpha))
                    result[(A, a)] = alpha
                else :
                    if verbose :
                        print("found %s in first(%s)" % (epsilon, _symbols(alpha)))
                    for b in gram.next(A, verbose) :
                        if verbose :
                            print(" => table[%s,%s] =" % (A, b), _rule(A, alpha))
                        result[(A, b)] = alpha
        return result
    def _slr_close (self, itemset, verbose) :
        result = set(itemset)
        while True :
            update = set()
            for left, head, tail in result :
                if len(tail) > 0 and not tail[0].final :
                    for right in self._rules[tail[0]] :
                        item = (tail[0], tuple(), right)
                        if item not in result :
                            update.add(item)
            if len(update) == 0 :
                break
            result.update(update)
        return tuple(sorted(result))
    def _slr_delta (self, I, X, verbose) :
        return self._slr_close([(A, head + (tail[0],), tail[1:])
                                for A, head, tail in I
                                if len(tail) > 0
                                if tail[0] == X],
                               verbose)
    def SLR (self, verbose=False) :
        gram = self.copy()
        gram.start = Symbol.new(self.start)
        gram.add(gram.start, [self.start])
        if verbose :
            print("*** added start symbol")
            print(gram)
            print()
        first = gram._slr_close([(gram.start, tuple(), (self.start,))],
                                verbose)
        number = { first : 0 }
        Delta = {}
        queue = set([first])
        if verbose :
            print("*** computing states")
            print("initial: 0")
            for item in first :
                print("  ", _item(item))
        while len(queue) > 0 :
            current = queue.pop()
            for X in gram.symbols(final=True) :
                new = gram._slr_delta(current, X, verbose)
                if len(new) == 0 :
                    continue
                elif new in number :
                    if verbose :
                        print("Delta(%s,%s) = %s" % (number[current], X, number[new]))
                    Delta[(number[current], X)] = number[new]
                else :
                    number[new] = len(number)
                    Delta[(number[current], X)] = number[new]
                    queue.add(new)
                    if verbose :
                        print("Delta(%s,%s) = %s (new)" % (number[current], X, number[new]))
                        for item in new :
                            print("  ", _item(item))
        items = dict([(num, val) for val, num in list(number.items())])
        if verbose :
            print()
        gram.next(gram.start, verbose=verbose)
        if verbose :
            print("\n*** building SLR table")
        result = SLR(gram)
        for i in items :
            for symbol in gram.symbols(final=True) :
                try :
                    j = Delta[(i, symbol)]
                except :
                    continue
                if verbose :
                    print(("Delta[%s,%s] = %s => table[%s,%s] ="
                           % (i, symbol, j, i, symbol)), end=' ')
                if symbol.final :
                    if verbose :
                        print("shift", j)
                    result[(i, symbol)] = ("shift", j)
                else :
                    if verbose :
                        print("goto", j)
                    result[(i, symbol)] = ("goto", j)
            for left, head, tail in items[i] :
                if (len(tail) == 0) and (left != gram.start) :
                    if verbose :
                        print(("state %s contains %s"
                               % (i, _item((left, head, tail)))))
                    for symbol in gram.next(left) :
                        if verbose :
                            print(("  %s in next(%s)"
                                   " => table[%s,%s] = reduce %s"
                                   % (symbol, left,
                                      i, symbol, _rule(left, head))))
                        result[(i, symbol)] = ("reduce", (left, head))
                elif ((left == gram.start) and (head == (self.start,))
                      and (len(tail) == 0)) :
                    if verbose :
                        print(("state %s contains %s"
                               % (i, _item((left, head, tail)))))
                        print("  => table[%s,%s] = accept" % (i, EOF))
                    result[(i, EOF)] = ("accept", None)
        return result
